package main.java.easy;

import main.java.structure.TreeNode;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * @Author: 郑国荣
 * @Date: 2023-07-31-20:35
 * @Description: 前序遍历
 */
public class PreOrderTraversal {
    public static ArrayList<Integer> list = new ArrayList<>();
    //递归算法
    public static List<Integer> preorderTraversal(TreeNode root){
        if (root!=null) {
            list.add(root.val);
            preorderTraversal(root.left);
            preorderTraversal(root.right);
        }
        return list;
    }

    //迭代算法
    public static List<Integer> preorderTraversal2(TreeNode root){
        TreeNode current = root;
        Stack<TreeNode> s = new Stack<>();
        while (current!=null){
            while (current!=null){
                list.add(current.val);
                if (current.right!=null){
                    s.push(current.right);
                }
                current = current.left;
            }
            if (!s.isEmpty()) current = s.pop();

        }
        return list;

    }


    public static void main(String[] args) {
        TreeNode root = new TreeNode(1,
                new TreeNode(2,new TreeNode(4),new TreeNode(5)),
                new TreeNode(3));
        // 1，2，4，5，3
        System.out.println(preorderTraversal2(root));
    }


}
